The present invention relates to the field of page printing systems, and specifically to image processors for page printing systems.
Page printing systems are well-known and utilize many different types of printers. For example, xerographic drums, light emitting diode (LED), and laser printers (a xerographic drum coupled with a laser) are all commonly used to form page printing systems.
The page printing system processes encoded page layout information to form a printed page. An image processor processes the page layout information to form (paint) decoded and uncompressed page image data. The image processor operates during a processing time. A printer operating at a preestablished printing rate prints the printed page during a printing time. The printer forms a scanned array of variable intensity pixels in response to page image data. A printer interface connects the image processor to the printer so that the page image data is transferred to the printer (shipout) and determines the intensity of the printed pixels which form the printed page.
In page printing systems, a printed page is formed by printing discrete picture elements (pixels) at fixed physical locations on an output medium such as paper. In general, the picture elements have different colors, different intensities and possibly other variable parameters. In general, to define pixels with such variable parameters, each pixel is represented by n bits of data. In one simple example, the color is black and white and no other parameters are variable. In such a simple example, the pixel can be represented by a single bit (n=1) of data where the bit is "on" (binary 1) for black and "off" (binary 0) for white. When the printing device is a matrix printer with only black and white provided, the printed page is defined by a matrix of small locations which register either a printed pixel (black) or a blank spot (white) at the pixel location. In a typical black/white laser printer, each pixel is a square measuring 1/300 inch on a side. Each pixel is much smaller than the smallest character or other shape to be printed, and therefore, each character or shape is formed by a number of pixels.
The printer operates by scanning the output medium along one of its two axes. The paper moves parallel to a direction P called the pageward direction. The laser beam scans in a direction S called the scanward direction. The scanward direction is orthogonal to the pageward direction. The laser beam is either on or off at each pixel location thereby forming either a printed pixel or blank spot as the laser beam scans across the page. A full line in the scanward direction is called a scanline. A full page of scanlines results in the printed page.
In order for a printed page to be formed by the printer, data for turning the laser beam on and off is supplied to the printer. The data which represents the printed page and which is supplied to the printer is called a "page image" or page image data. The page image is stored in the memory locations of a computer or other storage device. In an example where pixels are black or white, one bit (representing a pixel) can be stored in one memory cell. For an uncompressed digital representation having a one-for-one mapping from page image to printed page, each bit of the digital representation which constitutes a page image must have a correspondence to a pixel in the printed page both as to pixel color (black or white) and location.
In one example, the printed page is represented as a sequence of 2640 scanlines, each scanline composed of 2040 pixels. Correspondingly, the page image can be stored in 2640 memory sections with each section having 2040 cells. For example, each memory cell stores one bit of information with the value "0" denoting a white pixel and the value "1" denoting a black pixel. Each memory section corresponds to one scanline of the printed page and hence there is a one for one bit to pixel map from bits in the memory cells of memory to pixels on the printed page.
An alternative representation for a page image is achieved by using run-length encoding of sequences of pixels of the same color. In run-length encoding, scanlines are represented as sequences, each sequence being defined of the form (length) (color), where length denotes the number of pixels and "color" is either "W" for white or "B" for black.
There are many other types of digital encoded representations which can be used to represent page images. Although there is a correlation between the page image data stored in memory and the pixels of a printed page, that correlation is not required to be a one for one bit to pixel map.
The page image data itself is usually decoded from a "page layout". A "page layout" is an encoded representation of an entire printed page. A page layout is encoded using a page layout language. The page layout language employs a library or table of basic shapes called "glyphs". Glyphs include letters, numbers, symbols and characters or shapes of all types and sizes. The page layout language encompasses instructions which define where glyphs are to be located on a printed page. Additionally, the page layout language may specify other printing primitives (lines, splines, etc.) and define where these are to be located on a printed page. A page layout expressed in a page layout language is decoded to form page image data which correlates pixels to locations on a printed page.
An image processor is a device which accepts the high-level encoded page layout data stored in digital form and processes the page layout to form decoded page image data, also in digital form. The page image data is then transmitted to the printer to cause the printer to form the printed page.
Image processors face a number of limitations when used with page synchronous printers. Page synchronous printers print at a uniform rate during the printing of a page and permit stopping of the printer only between pages. In some prior art devices, image processors have been designed to process the encoded page layout data to generate the decoded page image data at a rate which can match the constant data rate required by such printers. Complex page layouts, however, can upset the balance between processing the page layout and printing the page image. If the image processor is too slow in supplying the page image data to the printer, then an incorrect page will be printed since page synchronous printers do not permit the stopping of the printing of a page at any point between the beginning and the end.
Early prior art devices used variations of a partial-page memory buffer storage scheme. A partial-page memory buffer is a dedicated memory area in which only a portion of an uncompressed page image is stored. Since memory devices were relatively expensive and page layouts were relatively simple, early image processing systems took advantage of processing speed to save memory.
One partial-page memory buffer scheme was implemented in a prior art image processor using alternating buffers. With alternating buffers, the page layout information is processed to fill one buffer with digital representations constituting a first part of the page image. After the first buffer is filled with a part of the page image, that first buffer is emptied to the page synchronous printer for printing the printed page, while the first buffer is being emptied to the printer, the second buffer is being filled by processing of the page layout to form the next portion of the page. After the first buffer is emptied and the second buffer is filled, the roles of the two buffers are exchanged. The second buffer is emptied to the printer while the first buffer is again filled. The process of alternately filling and emptying the buffers continues until the entire page image is printed.
A second variation of a partial-page memory buffer scheme was implemented in a prior art image processor utilizing a band memory allocation method. This method consists of using a dedicated memory area, typically on the order of 128 kilobytes. The memory composing the band is organized as a number of scanlines, each having a common width of the number of pixels contained in the horizontal line of the page image. the band is commonly referred to as a window, as it never contains more than a relatively small number of scanlines of the page image.
System operation employing the band allocation method consists of filling the band (painting) with the contents of the first few lines of the page image, starting the page synchronous printer, and updating each line of the band as the prior contents are printed. In this manner the band is scrolled down the page image, effectively racing the page-synchronous printer to keep new data flowing into the band. The painting operation is limited to be within the band. Since the band scrolls over the page image, the painting order is constrained to the band as scrolled.
Partial-page memory buffer systems like the ones previously described are commonly used in text-only systems or systems which have relatively simple graphics accompanying the text. At the time of their inception, the performance of these systems was commensurate with the state of development of graphics and text applications software.
As previously stated, prior art systems employing partial-page memory buffer schemes face the processing problem presented by "locally" complex page layouts. If the buffer-fill rate is not fast enough to process locally complex page layouts at any time during the processing, the page image data will not be available at the time it is needed by the printer, resulting in an error in the printed page.
Locally complex page layouts are characterized by a complexity which requires a great deal of processing time to form some part of the page image. Complexity typically arises in a situation where a large number of glyphs and/or other printing primitives are to be located in a relatively small area of the printed page. When many instructions (steps in the page layout) are required to be executed in order to form some local portion of the page image, then the image processor may produce the page image at a slower rate than the rate at which the printer prints. In prior art devices of the type described, the slower rate encountered when processing complex page layouts results in an error condition called an underrun error.
A subsequent major development in prior art was the introduction of a solitary full-page image buffer. This type of prior art requires that the uncompressed page image for the entire printed page be processed and stored in a full-page buffer before the printing operation commences. The full bitmap memory allocation method (full-page buffer) is, as its name implies, a dedicated memory area which contains the number of pixel locations required to contain a full bitmap of an image of a document.
Solitary full-page buffer systems, while solving the previous problem of underrun errors, face a different problem. These systems have an inter-page delay problem when multiple printed pages are to be printed in rapid succession. The inter-page delay results from the fact that the system cannot start filling the solitary full-page buffer with the page image data of the next page until it has finished using its current contents to print the current page. The inter-page delay causes the overall printing speed for many printed pages to be greatly reduced. Accordingly, it is desirable to avoid the inter-page delay in page printing systems.
The prior art devices have been unsuccessful in solving both the local complexity problem and the inter-page delay problem without resorting to the use of double full-page buffers within the same system. Full-bitmap memory allocation was made feasible by a decrease of the high cost of high density memory devices. A typical array for an 8.5.times.11 inch page at 300 dots per inch is on the order of one megabyte of memory. Accordingly, double full-page buffering involves an array on the order of two megabytes.
Virtual memory techniques are well-known in data processing systems. Virtual memory address space is typically employed as a method of working around constraints imposed by cost, space, or architecture. The logical memory can exceed the physical memory or vice-versa. In the prior art, the defined logical address space is implemented by some real address space and the need for translation from logical to real always exists.
A well-known algorithm for subdividing an image employs the Greek recursive method of subdividing the image into smaller and smaller regions. The regions have multiple pixels in both the x and y directions. The algorithm starts with an N-by-M pixel image. The algorithm first determines whether the entire N-by-M image can be represented as a single-color (for example, black or white rectangle) representation. If not, the N-by-M image is subdivided into N/x-by-M/y representations, where N/x and M/y are integers. Thereafter, each of these representations is examined to determine whether or not it can be represented as a single-color image. If not, each subdivision is further subdivided and examined. An (x * y) array tree formation is formed where the depth of each branch may vary in the structure. The treeing continues until finally each leaf of the tree (representing a subimage) can be expressed as a single-color representation. The treeing may continue all the way down to the pixel level. In such a system the patches (subimages of the image) can range all the way from the full N-by-M image all the way down to single pixels as a function of the particular image which is being represented.
A problem with the Greek recursive method is that the amount of cost and overhead required to practically implement such a system is believed to be prohibitive. It is probably simpler and less costly to implement a full-page memory buffering scheme.
In view of the above background, it is the objective of the present invention to provide an improved image processor and printing system which eliminates the risk of incurring underrun errors resulting from local complexity and reduces the inter-page delay problem while not using an excessive amount of physical memory.